1. Field of the Invention
The present invention relates to code generators and instruction set simulators for use as tools in developing software.
2. Description of the Related Art
Designers of electronic systems--as, for example, consumer electronics, communication systems and multimedia related products--more and more incorporate a programmable processor in their systems. Programmability offers them cost-effective hardware reuse and the flexibility to support last minute specification changes or to add new features to the system. The requirements of programmability, low cost and low power have resulted in a new class of application specific instruction set processors (ASIPs). These are a hybrid form of custom architectures and standard processors, offering an instruction set and hardware implementation which are optimized for a small number of applications.
A code generator and an instruction set simulator are the key tools to aid the designer when developing software. Because of the small number of applications to be mapped onto an ASIP, the effort to develop these tools should be as small as possible. Ideally, these tools should be reusable for a new ASIP without modification (i.e., they should be retargetable). A retargetable code generator has the extra advantage that late instruction-set changes are supported. It also aids in the design of an ASIP by providing quality measures (code size, execution time, resource utilization, and the like) on the mapping of applications to different hardware variations.
Code generators have different specific tasks to fulfill, of which the most important ones are code selection, register allocation and scheduling. Each of these tasks is implemented in a different program (called a code generator phase) which works on a different view of the processor. Processor models for existing code generators are just a set of these different views.
In the following, processor models and descriptions that are used in (retargetable) code generation for different types of processors will be reviewed.
The first retargetable code generators were designed for complex instruction set computers (CISCs). The architecture of these computers contains instructions with complicated operation patterns. Code selection was the most important task in these code generators and it performed register allocation and scheduling as a by-product. Code selection was implemented as tree pattern matching. As a consequence, the processor descriptions were tree or string grammars in which the production rules directly model the operation patterns available in the instruction set (Glanville and Graham, "A new method for compiler code generation," Proc. 5th Ann. ACM Symp. on Princ. of Prog. Lang., pages 231-240, 1978; Aho and Tjiang, "Code-generation using tree matching and dynamic programming," ACM Trans. on Prog. Languages and Systems, Vol. 11, No. 4, pages 491-516, 1989). Some descriptions were more complicated and contained matching preconditions related to hardware peculiarities, data types, storage locations and addressing modes.
In other approaches, a machine description is an enumeration of all instructions along with their corresponding simple register transfers. Also, the application is transformed in these register transfers. Code selection is performed by combining register transfers in the application into groups to be performed by one instruction (Davidson and Fraser, "The design and application of a retargetable peephole optimizer," ACM Trans. on Prog. Languages and Systems, Vol. 2, No. 2, pages 191-202, 1980).
More recent code generators have been developed for reduced instruction set computers (RISCs). In this case, the register allocation and scheduling tasks are more important than code selection and also need their specific information. For example, the processor description of the Marion retargetable code generator for RISCs (Bradlee, "Retargetable instruction scheduling for pipelined processors," Ph.D. thesis at the University of Washington, 1991) contains a declaration of storage elements and other resources in addition to the instruction set enumeration. The register transfers are then annotated with scheduling and resource utilization information.
Recent retargetable code generators for ASIPs (Paulin, et al., "DSP tool requirements for embedded systems: a telecommunications industrial perspective," J. VLSI Signal Processing, Vol. 9, No. 1, 1995; Fauth and Knoll, "Automated generation of DSP program development tools using a machine description formalism," Proc. IEEE of ICASSP 93, Minneapolis, 1993) also use different views of a processor. Retargeting the code generator to another processor means rewriting all these views.
Some retargetable code generators already introduced a graph as a processor model. These graph models however do not contain sufficient information for all phases in a code generator. Mueller (Mueller and Varghese, "Flow graph machine models in microcode synthesis," Proc. 16th Ann. Workshop on Microprogr., pages 159-167, 1983) used a graph model for performing the task of code selection by symbolic execution. For the processors he targeted, a by-product of this code selection was register allocation. Scheduling was performed separately, using a different view of the processor. Nowak (Nowak and Marwedel, "Verification of hardware descriptions by retargetable code generation," 26th ACM/IEEE Design Automation Conference, 1989) extracts a so-called connection-operation graph from a structural processor description. The description is a detailed net-list of the processor, including the controller and the instruction decoder, but this is often not available to the software developer. The connection-operation graph maps all conflicts on the instruction word and does not support additional checks for hardware conflicts. As a consequence, bus conflicts must be treated separately. The model only supports single-cycle operations.
Retargeting the above mentioned code generators to a new processor involves rewriting all the phase specific processor models. This is a large effort, especially because all views must be kept consistent. To solve this problem, some (e.g., Fauth and Knoll) try to derive the models from one processor description language (nML). This approach needs an analysis program for each model which is still a lot of work to implement.
In code generation approaches of prior art, the phases use different models, each containing a different view of the processor. This makes it difficult to have them work closely together.